Searching for examples similar to a given input example in a dictionary of digital content is often required in applications, for example, image encoding and decoding, texture synthesis, and the like. Digital content includes audio, image, and/or video content. Applications that perform image encoding and decoding often perform multiple dictionary searches. For example, an image being encoded can be divided into several image blocks and a dictionary search performed to find an example image or image block similar to each image block. If the dictionary searches are inefficient, the entire encoding process becomes slow and may not be acceptable.
An example of a conventional approach for dictionary search is a tree-based search. A tree-based search can be performed in a dictionary organized as a tree structure such that leaf nodes of the tree represent similar content. Search is performed by making a decision at each node of the tree regarding which branch of the tree to follow to continue the search. Since each search requires traversing several levels of the tree, each level requiring one or more comparisons of image blocks, the tree-based search is slow.
Conventional tree-based searches also have a drawback in that examples belonging to two different leaf nodes of the tree are not guaranteed to be similar. For example, two neighboring leaf nodes may be neighbors in the tree structure but an image taken from one of the leaf nodes may be very different from an image taken from the neighboring leaf node. As a result, a slight error in traversing the tree caused by taking an incorrect branch of the tree at a higher level of the tree may result in arriving at a leaf node that does not comprise examples similar to the input example. For these reasons, images encoded/decoded using these techniques may have poor quality or the encoding/decoding process may have poor performance.